package org.shj.suanfa

/**
 * 最大连续子序列和： 给出N个整数，求出总和最大的连续子序列。如果全部是负数，则最大和为0
 */
object MaxSumInSeq {
  def main(args: Array[String]): Unit = {
    val arr = List(4, -3, 5, -2, -1, 2, 6, -2)
//    method1(arr) // O(N^3) 算法，效率极低
//    method2(arr)  // O(N^2) 算法
    method3(arr)  // O(N*logN) 算法
    method4(arr)  // O(N) 算法
  }
  
  
  def method1(arr: List[Int]) = {
    var sum = Int.MinValue
    var tmp = 0
    for(i <- 0 until arr.length){
      for(j <- i+1 until arr.length){
        tmp = 0
        for(k <- i to j){
          tmp += arr(k)          
        }
        if(tmp > sum){
          println(i + "," + j)
          sum = tmp
        }
      }
    }
    println(sum)
  }
  
  /**
   * 对method1的改进
   */
  def method2(arr: List[Int]) = {
    var sum = Int.MinValue
    
    for(i <- 0 to arr.length-1){
      var s = 0
      for(j <- i to arr.length-1){
        s += arr(j)
        if(s > sum){
          sum = s
        }
      }
    }
    print(sum)
  }
  
  /**
   * 使用分治算法，把序列分成大致等长的序列（左序列和右序列），那么问题的解有三种情况：
   * 1. 最大子序列在左序列中， 
   * 2. 最大子序列在右序列中
   * 3. 最大子序列为： 左序列中（包含最后一个元素）中的一部分 + 右序列中（包含第一个元素）的一部分
   * 
   * 利用递归思想，把左右序列分别再次拆分
   */
  def method3(arr: List[Int]) {
    println(maxSeq(arr))
  }
  
  private def maxSeq(arr: List[Int]): Int = {
    if(arr.length == 1){
      arr(0)
    }else if(arr.length == 2){
      Array(arr(0), arr(1), arr(0) + arr(1)).max
    }
    else{
      var mid = arr.length / 2
      val leftAndRight = arr.splitAt(mid)
      var maxLeft = maxSeq(leftAndRight._1)
      var maxRight = maxSeq(leftAndRight._2)
      
      var maxLeftIncludeLast = maxIncludeLast(leftAndRight._1)
      var maxRightIncludeFirst = maxIncludeFirst(leftAndRight._2)
      Array(maxLeft, maxRight, maxRightIncludeFirst + maxLeftIncludeLast).max
    }
  }
  
  private def maxIncludeLast(arr: List[Int]): Int = {
    var max = arr(arr.length - 1)
    var sum = max
    for(i <- 0 to arr.length-2){
      sum += arr(arr.length-2 - i)
      if(sum > max){
        max = sum
      }
    }
    max
  }
  
  private def maxIncludeFirst(arr: List[Int]): Int = {
    var max = arr(0)
    var sum = max
    for(i <- 1 until arr.length){
      sum += arr(i)
      if(sum > max){
        max = sum
      }
    }
    max
  }
  
  
  def method4(arr: List[Int]) {
    var max = 0
    var maxEndingHere = 0
    for(i <- 0 to arr.length -1 ){
      maxEndingHere += arr(i)
      if(maxEndingHere < 0){
        maxEndingHere = 0
      }
      max = if (max > maxEndingHere ) max else maxEndingHere
    }
    print(max)
  }
}